package map;

import java.util.Arrays;
import java.util.Objects;

/**
 * 模拟实现HashMap 关于传递泛型类 的代码*/
public class HashBucket<K,V> {
    public static class Node<K, V> {
        public K key;
        public V value;
        public Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        //我们我们需要在Node节点内重写hashCode方法，以保证在相同key值时，其存储在相同位置、

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?, ?> node = (Node<?, ?>) o;
            return Objects.equals(key, node.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }

    //创建哈希桶底层数组 与 计数器
    public Node<K,V>[] array;
    public int usedSize;

    //创建负载因子
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBucket() {
        array = new Node[10];
    }

    /**
     * 在哈希桶中插入数据
     * 需要考虑：负载因子 和 相同数据插入 的问题
     */
    public void put(K key, V value) {
        //判断对应链表中是否存在相同key值节点，若是，则修改value后return
        Node<K,V> node = new Node<>(key,value);

        int index = node.hashCode()%array.length;
        Node<K,V> cur = array[index];

        while(cur!=null) {
            if(cur.equals(node)) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }

        //代码走到此处则说明在哈希桶中不存在相同key值的节点，故尾插
        Node<K,V> prev = null;
        cur = array[index];
        while(cur!=null) {
            prev = cur;
            cur = cur.next;
        }

        //当cur==null时 prev会为空，故为了避免空指针异常，需要对prev进行判定
        if(prev!=null) {
            prev.next = node;
        } else {
            //prev为空，说明链表中无节点，直接头插
            node.next = array[index];
            array[index] = node;
        }
        usedSize++;
        //插入完成之后需要判断负载因子，若是负载因子达到上限则需要resize
        if((usedSize*1.0f/array.length)>=DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }
    //扩容
    private void resize() {
        //创造新的数组，将原数组所有元素重新hash插入
        Node<K,V>[] newArray = new Node[array.length*2];
        //本循环遍历原数组中所有链表
        for(int i = 0; i < array.length; i++) {

            //本循环遍历该链表中所有节点
            Node<K,V> cur = array[i];
            while(cur != null) {
                //保存下一节点
                Node<K,V> nextNode = cur.next;

                //将当前遍历的节点尾插到新链表中
                int newIndex = cur.hashCode()%newArray.length;
                Node<K,V> newCur = newArray[newIndex];
                Node<K,V> prev = null;
                while(newCur!=null) {
                    prev = newCur;
                    newCur = newCur.next;
                }
                if(prev!=null) {
                    prev.next = cur;
                } else {
                    //prev为空，说明链表中无节点，直接头插
                    cur.next = newArray[newIndex];
                    newArray[newIndex] = cur;
                }

                cur = nextNode;
            }
        }
        this.array = newArray;
    }

    /**
     * 在哈希桶中获取数据*/
    public V get(K key) {
        //由于key具有唯一性，故通过key来进行查找
        //创建临时节点进行操作--》这个问题亟待解决
        V val = (V)"-1";
        Node<K,V> tmp = new Node<>(key,val);

        int index = tmp.hashCode()%array.length;
        Node<K,V> cur = array[index];
        while(cur!=null) {
            if(cur.key.equals(key)) {
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
}
